#ifndef SOCIAL_GRAPH_H
#define SOCIAL_GRAPH_H

#include "Utility.h"
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

class Graph{
public:
	Graph(int _num_partition_file, int _num_true_partitions, string in_dir);
	~Graph(){};

	int GetNumPartition(){return num_partitions;};
	int GetUserPartition(int user_id){return node_partition_map[user_id];};
	
	// get the distance between the point and the partition's pivot, should exclude the point is the pivot itself
	int GetPointToPivotDist(int partition_idx, int node_id){return pivot_to_all_dist[partition_idx][node_id];};

	// get one partition to all partition distance
	vector<int>& GetParitionDist(int user_partition){return partition_dist[user_partition];};
	// get pivot to all disktance
	vector<int>& GetPivotToAllDisk(int user_partition){return pivot_to_all_dist[user_partition];};

	// init a new query
	void InitPointTranverse(int node);
	// if the distance larger than threshold, no need to tranverse, return -1 if threshold is excceed
	double GetSocialRelevance(int target_node, double min_relevance, int op_level);

	int GetNearestNeighborDist(int target_node){return adj_lists[target_node][0].second;};

	// Get Number of Nodes
	int GetNumNodes(){return num_nodes;};

	int GetMaxSocialDistance(){return this->max_social_distance;};

	double GetElapsedTime(){return elapsedTime;};
	void ResetTimer(){elapsedTime = 0;num_ops=0;};
	int GetNumOps(){return num_ops;};
	int GetProcessedNode(){return node_processed;};

	// sample a user based degree level of the user, degree_level 0, 0-33%, degree_level 1, 33-67%, degree level 2, 67%-100%
	int SampleUser(int degree_level);

private:
	int num_nodes;			

	vector<int> nn2hop; // nearest distance for 2 hop neighbour for each node

	vector<vector<pair<int,int> > > adj_lists;	// graph adjacency list

	int num_partitions;
	vector<vector<int> > partition_dist;		// distance between different partitions
	
	unordered_map<int,int> node_partition_map;	// map between the user/node to the partition it belongs
	vector<int> pivot_nodes;					// each partition has a pivot node
	vector<vector<int> > pivot_to_all_dist;		// distance from the pivot to all other nodes

	int max_social_distance;// maximum distance between two nodes in the social graph
	void FindMaxSocialDistance(); // maximum social distance between any two nodes

	vector<pair<int,int> > node_degree_rank; // store all node based on their degree, first element store the degree and second element store index

	// for temproary tranverse
	int source_node;
	int node_processed;
	vector<int> dist_from_user;
	vector<bool> dist_determined;
	vector<double> social_rel;
	int minimum_dist_so_far;
	double max_rel_so_far;
	double elapsedTime;
	int num_ops;
	vector<pair<int,int> > target_node_neighbour; // if index of the entry equal to target then it is neigbour of target

	vector<vector<int> > not_finalized_nodes;
	int vec_pos; // vector position to keep reference to the distance queue
	//set<pair<int,int> > not_finalized_nodes;	// nodes that has not been confirmed distance
	//vector<set<pair<int,int> >::iterator > iter_memory;	// position in the size
	
};

#endif